logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premise ...

, the

contrapositive In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as proof by contraposition. The contrapositive of a statem ...

of a conditional statement is formed by negating both terms and reversing the direction of inference. More specifically, the contrapositive of the statement "if ''A'', then ''B''" is "if not ''B'', then not ''A''." A statement and its contrapositive are logically equivalent, in the sense that if the statement is true, then its contrapositive is true and vice versa. In mathematics, proof by contrapositive, or proof by contraposition, is a rule of inference used in proofs, where one infers a conditional statement from its contrapositive. In other words, the conclusion "if ''A'', then ''B''" is inferred by constructing a proof of the claim "if not ''B'', then not ''A''" instead. More often than not, this approach is preferred if the contrapositive is easier to prove than the original conditional statement itself. Logically, the validity of proof by contrapositive can be demonstrated by the use of the following

truth table A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...

, where it is shown that ''p'' → ''q'' and ''

\lnot

q'' → ''

\lnot

p'' share the same truth values in all scenarios:

Difference with proof by contradiction

Proof by contradiction In logic and mathematics, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition, by showing that assuming the proposition to be false leads to a contradiction. Proof by contradiction is also known ...

: Assume (for contradiction) that

\neg A

is true. Use this assumption to prove a

contradiction In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle's ...

. It follows that

\neg A

is false, so

A

is true. Proof by contrapositive: To prove

A \to B

, prove its contrapositive statement, which is

\neg B \to \neg A

Example

Let

x

be an integer. :To prove: ''If ''

x^2

''is even, then ''

x

'' is even. Although a

direct proof In mathematics and logic, a direct proof is a way of showing the truth or falsehood of a given statement by a straightforward combination of established facts, usually axioms, existing lemmas and theorems, without making any further assumptions. ...

can be given, we choose to prove this statement by contraposition. The contrapositive of the above statement is: :''If ''

x

'' is not even, then ''

x^2

''is not even.'' This latter statement can be proven as follows: suppose that ''x'' is not even, then ''x'' is odd. The product of two odd numbers is odd, hence

x^2=x\cdot x

is odd. Thus

x^2

is not even. Having proved the contrapositive, we can then infer that the original statement is true. (p. 50).

References

{{DEFAULTSORT:Proof By Contrapositive Mathematical proofs Methods of proof Propositional calculus

Difference with proof by contradiction

Example

See also

References